package com.app.sort;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] data = new int[]{20, 40, 80, 33, 111, 47, 21, 90, -1};
        HeapSort hs = new HeapSort();
        hs.heap_array(data, data.length - 1);

        for (int i = 0; i < data.length - 1; i++) {
            int tmp = data[0];
            data[0] = data[data.length - 1 - i];
            data[data.length - 1 - i] = tmp;
            hs.heap_array(data, data.length - 2 - i);
        }
        System.out.println(Arrays.toString(data));

    }

    public void heap_array(int[] data, int end) {
        int last_p = end;
        //i是第一个非叶子节点
        for (int i = (last_p - 1) / 2; i >= 0; i--) {
            heapify(data, i, last_p);
        }
    }

    public void heapify(int[] data, int start, int end) {
        int value = data[start];
        int current_p = start;
        int left_p = 2 * current_p + 1;
        while (left_p <= end) {
            if (left_p < end && data[left_p] < data[left_p + 1]) {
                left_p++;
            }
            if (data[left_p] < value) {
                break;
            } else {
                data[current_p] = data[left_p];
                current_p = left_p;
                left_p = current_p * 2 + 1;
            }
        }
        data[current_p] = value;
    }


    public static class Heap {
        private int[] data;
        private int maxSize;

        public Heap(int[] data, int maxSize) {
            this(data);
            this.maxSize = maxSize;
        }

        private Heap(int[] data) {
            int last_p = data.length - 1;
            //i是第一个非叶子节点
            for (int i = (last_p - 1) / 2; i >= 0; i--) {
                heapify(data, i, last_p);
            }
            this.data = data;
        }

        private void heapify(int[] data, int start, int end) {
            int value = data[start];
            int current_p = start;
            int left_p = 2 * current_p + 1;
            while (left_p <= end) {
                if (left_p < end && data[left_p] < data[left_p + 1]) {
                    left_p++;
                }
                if (data[left_p] < value) {
                    break;
                } else {
                    data[current_p] = data[left_p];
                    current_p = left_p;
                    left_p = current_p * 2 + 1;
                }
            }
            data[current_p] = value;
        }


        private void checkSize() {
            if (data.length + 1 > maxSize) {
                throw new IllegalStateException("beyond max size");
            }
            data = Arrays.copyOf(data, data.length + 1);
        }

        public int insert(int value) {
            checkSize();
            int position = data.length - 1;
            data[position] = value;

            int current_p = position;
            int parent_p = (position - 1) / 2;
            while (current_p > 0) {
                if (data[parent_p] > value) {
                    break;
                } else {
                    data[current_p] = data[parent_p];
                    current_p = parent_p;
                    parent_p = (current_p - 1) / 2;
                }
            }
            data[current_p] = value;
            return position;
        }


        /**
         * @return 返回最大值，也就是堆顶的值
         */
        public int remove() {
            int root = data[0];
            int last = data[data.length - 1];
            data[0] = last;
            data = Arrays.copyOf(data, data.length - 1);
            if (data.length == 0) {
                return root;
            }
            //从顶点开始调整
            int current_p = 0;
            int l = current_p * 2 + 1;
            int value = data[current_p];
            while (l < data.length) {
                if (l < data.length - 1 && data[l] < data[l + 1]) {
                    l++;  //右孩子大
                }
                if (data[l] <= value) {
                    break;
                } else {
                    data[current_p] = data[l];
                    current_p = l;
                    l = current_p * 2 + 1;
                }
            }
            data[current_p] = value;
            return root;
        }

        public int size() {
            return data.length;
        }

        @Override
        public String toString() {
            return Arrays.toString(data);
        }
    }
}
